# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
# preorder=[1,2]
# inorder=[2,1]


def dfs(preorder,inorder,index,preorder_left,preorder_right,inorder_left,inorder_right):
    #出口条件
    if preorder_left>preorder_right:
        return None
    #前序遍历中的第一个节点就是根节点
    preorder_root=preorder_left
    #在中序遍历中定位根节点(这里使用了一个hash表来进行定位操作)
    inorder_root=index[preorder[preorder_root]]

    #先把根节点建立出来
    root=TreeNode(preorder[preorder_root])
    #得到左子树中的节点数目
    size_left_subTree=inorder_root-inorder_left
    #递归地构造左子树并连接到根节点
    root.left=dfs(preorder,inorder,index,preorder_left+1,preorder_left+size_left_subTree,inorder_left,inorder_root-1)

    root.right=dfs(preorder,inorder,index,preorder_left+size_left_subTree+1,preorder_right,inorder_root+1,inorder_right)

    return root



def buildTree(preorder,inorder):
    n=len(preorder)
    index={element: i for i, element in enumerate(inorder)}
    return dfs(preorder,inorder,index,0,n-1,0,n-1)
buildTree(preorder,inorder)